#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class UFset {
  private:
	vector<int> parent; //使用的是id识别每个字母
	vector<double> weight;

  public:
	UFset(int n) {
		for (int i = 0; i < n; ++i) {
			parent.push_back(i);
			weight.push_back(1.0);
		}
	}
	void Union(int x, int y, double value) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx == rooty)
			return;
		parent[rootx] = rooty; //并查集操作,将rootx的根节点设置为rooty
		weight[rootx] = weight[y] * value / weight[x];
	}

	int find(int x) {
		if (x != parent[x]) {
			int origin = parent[x];
			parent[x] = find(parent[x]);
			weight[x] *= weight[origin];
		}
		return parent[x];
	}

	double Ratio(int x, int y) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx == rooty)
			return weight[x] / weight[y];
		else
			return -1.0;
	}
};
vector<double> calcEquation(vector<vector<string>> &equations, vector<double> &values, vector<vector<string>> &queries) {
	int equationsize = equations.size();
	unordered_map<string, int> element;
	UFset UnionFind(2 * equationsize);
	int id = 0; //对每个字母进行编码
	//将条件的每个节点插入到散列表当中
	for (int i = 0; i < equationsize; ++i) {
		if (element.find(equations[i][0]) == element.end()) {
			element[equations[i][0]] = id;
			id++;
		}
		if (element.find(equations[i][1]) == element.end()) {
			element[equations[i][1]] = id;
			id++;
		}
		UnionFind.Union(element[equations[i][0]], element[equations[i][1]], values[i]);
	}
	//查找各个问题的组合,并给出结果
	int queriesize = queries.size();
	vector<double> res;
	for (int i = 0; i < queriesize; ++i) {
		if (element.find(queries[i][0]) == element.end() || element.find(queries[i][1]) == element.end())
			res.push_back(-1.0);
		else {
			res.push_back(UnionFind.Ratio(element[queries[i][0]], element[queries[i][1]]));
		}
	}
	return res;
}

int main() {
	vector<vector<string>> equations = {{"a", "b"}, {"b", "c"}};
	vector<double> values = {2.0, 3.0};
	vector<vector<string>> queries = {{"x", "x"}, {"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}};
	calcEquation(equations, values, queries);
	return 0;
}